package leetcode_en

import (
	"go-study/src/leetcode"
	"go-study/src/utils"
)

/**
 * @Description: 836. Rectangle Overlap
 * @Keyword: 矩形重叠
 * @Author: kami
 * @Date: 2022/2/12 9:14
 **/
func isRectangleOverlap(rec1 []int, rec2 []int) bool {
	return rec1[0] < rec2[2] && rec2[0] < rec1[2] && rec1[1] < rec2[3] && rec2[1] < rec1[3]
}

/**
 * @Description: 852. Peak Index in a Mountain Array
 * @Keyword: 找山顶
 * @Author: kami
 * @Date: 2022/2/12 9:41
 **/
func peakIndexInMountainArray(arr []int) int {
	for i := 1; i < len(arr); i++ {
		if arr[i] < arr[i-1] {
			return i - 1
		}
	}
	return 0
}

/**
 * @Description: 859. Buddy Strings
 * @Keyword: 交换等于
 * @Author: kami
 * @Date: 2022/2/12 9:45
 **/
func buddyStrings(s string, goal string) bool {
	if len(s) != len(goal) {
		return false
	}
	var diff []int
	var exist = new([26]int)
	var isSameExist bool
	for i := 0; i < len(s); i++ {
		if s[i] != goal[i] {
			diff = append(diff, i)
		}
		if exist[s[i]-'a'] > 0 {
			isSameExist = true
		} else {
			exist[s[i]-'a'] += 1
		}
	}
	size := len(diff)
	if size > 2 || size == 1 {
		return false
	}
	if size == 2 && s[diff[0]] == goal[diff[1]] && s[diff[1]] == goal[diff[0]] {
		return true
	}
	if size == 0 && isSameExist {
		return true
	}
	return false
}

/**
 * @Description: 860. Lemonade Change
 * @Keyword: 枚举场景
 * @Author: kami
 * @Date: 2022/3/1 21:23
 **/
func lemonadeChange(bills []int) bool {
	var five, ten int
	for _, bill := range bills {
		switch bill {
		case 5:
			five++
		case 10:
			if five <= 0 {
				return false
			}
			five--
			ten++
		case 20:
			if ten > 0 && five > 0 {
				ten--
				five--
			} else if five >= 3 {
				five -= 3
			} else {
				return false
			}
		}
	}
	return true
}

/**
 * @Description: 867. Transpose Matrix
 * @Keyword: 转换矩阵
 * @Author: kami
 * @Date: 2022/3/1 21:44
 **/
func transpose(matrix [][]int) [][]int {
	m, n := len(matrix), len(matrix[0])
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int, m)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			res[j][i] = matrix[i][j]
		}
	}
	return res
}

/**
 * @Description: 868. Binary Gap
 * @Keyword: 数字转二进制，查找1之间0最多的个数
 * @Author: kami
 * @Date: 2022/3/19 20:39
 **/
func binaryGap(n int) int {
	var count = -32
	var max = 0
	for n > 0 {
		if (n & 1) == 1 {
			max = utils.GetMax(max, count)
			count = 0
		}
		count++
		n >>= 1
	}

	return max
}

/**
 * @Description: 872. Leaf-Similar Trees
 * @Keyword: 前序遍历
 * @Author: kami
 * @Date: 2022/4/3 9:38
 **/
func leafSimilar(root1 *leetcode.TreeNode, root2 *leetcode.TreeNode) bool {
	res1 := dfsLeafNode(root1, []int{})
	res2 := dfsLeafNode(root2, []int{})
	if len(res1) != len(res2) {
		return false
	}
	for i := 0; i < len(res1); i++ {
		if res1[i] != res2[i] {
			return false
		}
	}
	return true
}

func dfsLeafNode(root *leetcode.TreeNode, res []int) []int {
	if root.Left == nil && root.Right == nil {
		res = append(res, root.Val)
		return res
	}
	if root.Left != nil {
		res = dfsLeafNode(root.Left, res)
	}
	if root.Right != nil {
		res = dfsLeafNode(root.Right, res)
	}
	return res
}
